class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stacks = new Stack<>();
        int max = 0;
        int width, top;
        for (int i = 0; i < heights.length; i++) {
            if (stacks.isEmpty() || heights[stacks.peek()] <= heights[i]) {
                stacks.push(i);
                continue;
            }
            while (!stacks.isEmpty() && heights[stacks.peek()] > heights[i]) {
                top = stacks.pop();
                width = stacks.isEmpty() ? i : i - stacks.peek() - 1;
                max = Math.max(max, width * heights[top]);
            }
            stacks.push(i);
        }

        while (!stacks.isEmpty()) {
            top = stacks.pop();
            width = stacks.isEmpty() ? heights.length : heights.length - stacks.peek() - 1;
            max = Math.max(max, width * heights[top]);
        }
        return max;
    }
}